The present invention is generally directed to computer programs for generating schedules and, more particularly, relates to a method for generating a schedule which is based on resource assignments, and optimally uses the available resources to complete a list of tasks.
Scheduling programs have gained considerable popularity among project-oriented professions such as product engineering companies, construction firms, and manufacturing plants. Scheduling programs allow a project manager to organize and track the development of a project. In the most general sense, a scheduling program operates by receiving an input of project-related information, generating a schedule based on this information, and then graphically or in a tabular manner, displaying the details concerning the status of the project, projected completion date, anticipated delays, etc.
The critical path method (CPM) of scheduling is used in a significant number of scheduling programs. CPM scheduling generally operates by receiving a list of tasks, each task having varying restrictions or constraints, and generating a schedule based on the task restrictions or constraints. More specifically, a set of tasks are provided to the scheduling program. Each task represents a specific job or discrete amount of work that must be performed on a project. Additionally, each task has a set of restrictions or constraints which dictate when and how long the task should be performed. To generate a meaningful schedule, CPM scheduling requires the input of information which identifies when each task is to be performed. This information can be provided by specifying constraints such as: a start date and a finish date, a start date and a task duration, a task duration and a finish date, or a task duration and a start or finish date which is dependent upon another task. If this information is not specified, the typical CPM scheduling program will assume the start date for each task to be the current date, and the duration of the task will default to a specific granularity such as one day, one week, etc.
Linking information concerning one or more of the tasks may also be entered. For instance, if a project consists of three tasks (Task 1, Task 2, and Task 3), the user may specify that Task 1 must be completed before Task 2 and Task 2 must be completed before Task 3. This information can be provided in the form of entering a start date for Task 2, which is equivalent to the finish date for Task 1, or by specifying that the start date for Task 2 is dependent upon the completion of Task 1. The latter method is referred to as a link.
Once the user enters the task information, a CPM scheduling program generates a schedule based on the provided task constraints. This is accomplished by performing a forward pass in which each task is examined. At the completion of the forward pass, a schedule is created that starts on the start date of the first task that can be scheduled and satisfies all of the provided task constraints. Next, the critical path for the project is determined. The critical path can be defined as the longest duration path through the network of task dependencies. The critical path is calculated by performing a backward pass from the last finish date to the earliest start date.
CPM scheduling programs are most beneficial for projects in which the tasks have dependencies on each other. Because of this, they are well suited for product-oriented projects which inherently have tasks that must be performed in a specific order. As an example, in building a house, the tasks of laying a foundation, framing the house, and shingling the roofing must be performed in this order. There are, however, many situations where the order of performing certain tasks of a project are arbitrary. For instance, in publishing a news letter, the order in which the articles are written is arbitrary. CPM scheduling programs typically do not produce meaningful results when the tasks do not have dependencies. As an example, if the three tasks (Task 1, Task 2 and Task 3) are not required to be performed in any specific order (i.e., do not have any dependencies), a CPM scheduling program will generate a xe2x80x9cflat schedulexe2x80x9d as illustrated in Schedule Example 1. 
The problems associated with flat scheduling are evident when the tasks are viewed with respect to the resources assigned to the tasks. For instance, if a single resource is assigned to each of these three tasks, the flat schedule indicates that the resource will be required to work on three tasks at the same time. This results in xe2x80x9coverloadingxe2x80x9d the resource. Alternatively, separate resources (Resource 1, Resource 2 and Resource 3) could be assigned to each of the three tasks respectively. This would result in a 100% utilization of Resource 2 and Resource 3; however, after the completion of Task 1, Resource 1 would be idle. This is referred to as xe2x80x9cunder-utilizingxe2x80x9d a resource.
To avoid the generation of a flat schedule by a CPM scheduling program, the user is required to enter artificial dependency information such as links or start dates. Thus, to avoid the flat schedule shown in Schedule Example 1, the user could define the start date of Task 2 as dependent upon the completion of Task 1, and the start date of Task 3 as dependent upon the completion of Task 2. For projects with several tasks, this process may require a significant amount of effort for the user. Thus, there is a need for a scheduling program which can generate a meaningful schedule for a set of non-dependent tasks. Furthermore, there is a need for a scheduling program that can generate a meaningful schedule for a set of non-dependent tasks without requiring the input of artificial constraints such as start dates or dependencies.
A schedule in which resources are overloaded and/or under-utilized is referred to as an xe2x80x9cunbalancedxe2x80x9d schedule. As previously illustrated, CPM scheduling programs are susceptible to producing unbalanced schedules. One method that has been developed to address this deficiency in CPM scheduling programs is referred to as xe2x80x9clevelingxe2x80x9d. The leveling process operates separately from the CPM scheduling and is designed to balance the resource utilization of a schedule. In this process, an overloaded resource is identified, and the task or tasks causing the first instance of the overload are determined. Next, adjustments are made to the start and/or finish dates of the task or tasks causing the overload to reduce the resource usage to 100%. Because this adjustment may result in changing the critical path, each time a leveling adjustment is made, the critical path must be recalculated before further leveling adjustments can be performed. Thus, for each leveling adjustment, a forward pass is performed to reschedule the tasks, and a backward pass is performed to recalculate the critical path. Depending on the number of tasks and the amount of overloading, this process can require a significant amount of iterative processing which wastes valuable processor time. Thus, there is a need for a method of scheduling which produces a balanced schedule. There is also a need for a method of scheduling that efficiently and quickly produces a balanced schedule which maximizes the use of the available resources.
CPM scheduling programs operate on a task-oriented basis. A problem that results from task-oriented scheduling is the tendency to under-utilize the available resources. The following example is illustrative of this problem. If the following information is provided to a CPM scheduling program:
Resource 1 (R1) is assigned to Task 1,
Resources 1 and 2 (R1,R2) are assigned to Task 2, and
Resource 2 is assigned to Task 3,
upon completion of the scheduling process, the schedule shown in Schedule Example 1 would be created. Next, upon completion of the leveling process, a possible outcome of the schedule is shown in Schedule Example 2. 
In Schedule Example 2, Task 2 has been scheduled to start upon the completion of Task 1 and Task 3 has been scheduled to start upon the completion of Task 2. Task 2 is scheduled to begin after Task 1 in order to avoid overloading of Resource 1. This results, however, in under-utilizing Resource 2, which is not scheduled during the time Resource 1 is working on Task 1. This under-utilization occurs as a result of using task-oriented scheduling. CPM scheduling with leveling would not allow Resource 2 to be scheduled to work on Task 2 in parallel with Resource 1 working on Task 1 because that would appear to overload Resource 1.
A second possible schedule that could result from the input information provided above is shown in Scheduling Example 3. 
In Scheduling Example 3, Resource 2 has been scheduled to work on Task 3 in parallel with Resource 1 working on Task 1, and Task 2 has been scheduled to begin upon the completion of Task 3. In this schedule, Resource 1 is under-utilized during the time after the completion of Task 1 and prior to the start of Task 2. Again, the under-utilization occurs as a result of task-oriented scheduling. Because Resource 2 is assigned to both Task 2 and Task 3, Task 2 can not begin until the completion of Task 3.
An alternative to task-oriented scheduling is assignment-oriented scheduling. In Schedule Examples 2 and 3, Task 2 can be viewed as consisting of two assignments, one assignment for Resource 1 and another for Resource 2. By performing assignment-oriented scheduling in Schedule Example 2, Resource 2 could begin working on Task 2 in parallel with Resource 1 working on Task 1. The resulting schedule is shown in Schedule Example 4. 
Likewise, by utilizing assignment-oriented scheduling in Schedule Example 3, Resource 1 can begin work on Task 2 upon the completion of Task 1, thereby avoiding the under-utilization of Resource 1. Scheduling Example 5 illustrates a schedule that could result from use of assignment-oriented scheduling. 
Thus, to allow for the most efficient allocation of resources, there is a need for a method to generate a schedule which is assignment-oriented rather than task-oriented. There is also a need for a method which allows the independent scheduling of individual assignments of a task. This is illustrated in Scheduling Example 4 and 5 by splitting Task 2 into two independent assignments.
CPM scheduling programs schedule tasks linearly, which contributes to the under-utilization of resources. Linear scheduling implies that once a task is started, work must continue on that task until it is completed. Thus, in Schedule Example 2, if the start of Task 2 is dependent upon the completion of Task 1, then Resource 2 could not work on Task 2 in parallel with Task 1 as illustrated in Schedule Example 4. Thus, Resource 2 will be under-utilized. An alternative to linear scheduling is to view each task as a series of smaller assignments which can be performed independently. For example, if the duration of Task 3 is one month, then Task 3 can be viewed as four (4) one week assignments or twenty (20) one day assignments. Each of these assignments can then be independently scheduled and Schedule Example 6 could result. 
In Schedule Example 6, Task 3 has been subdivided into two assignments. The first assignment is performed in parallel with Task 1 to avoid the under-utilization of Resource 2 during this period of time. Because CPM scheduling utilizes linear scheduling, a CPM-based scheduling program could not subdivide Task 3 as illustrated. Thus, there is a need for a scheduling method which subdivides a task or assignment into components which can be individually scheduled, and generates a maximum resource utilization schedule based on these components.
Thus, there are several problems and deficiencies associated with CPM scheduling programs. Some of these problems, such as flat scheduling, can be alleviated by burdening the user with the requirement of creating artificial constraints upon the entered tasks. Other problems, such as the under-utilization of resources can not be alleviated within the constraints of CPM scheduling. Therefore, there is a need for an efficient method of scheduling that will generate meaningful schedules which maximize resource utilization by performing assignment-oriented scheduling.
The present invention satisfies the above-described needs by providing a system and a method for generating a schedule for completing the tasks of a project by sequentially scheduling individual assignments for a resource in accordance with a resource calendar. First information is received concerning the resources and the tasks. This information is then used as the basis for generating assignments, which can be individually scheduled to a resource, and a resource calendar that identifies available time-slots for each resource. Next, the assignments are sequentially scheduled, into available time-slots for the various resources assigned to the project. The resulting schedule is a balanced schedule which maximizes the utilization of the available resources.
One aspect of the present invention is a system and a method for generating assignments for a task and individually scheduling the assignments to a resource. In one embodiment, the assignments are generated based upon the task constraints associated with each task. The task constraints must identify the resources that are assigned to a task and either a required work-amount for each of these resources or a total work-amount for the task. The assignments are generated by dividing each task by the number of assigned resources and then identifying which resource is associated with which assignment. Next, the work-amount is identified for each assignment. One method to identify the work-amount is to equate the work-amount for each assignment to the work-amount identified in the task constraints. Another method is to divide the total work-amount for the task by the number of assignments and to set the work-amount for each assignment to this value. This aspect of the invention is advantageous because scheduling on an assignment basis allows resources to be scheduled at maximum utilization.
Another aspect of the present invention is a system and a method for generating a schedule which represents the order for a group of available resources to complete the tasks required for a project. First, input information is received which identifies the available resources and tasks that must be performed by these resources. A resource calendar identifies the resources available to work on a project and any constraints that are associated with the resources. A task list identifies the tasks that must be performed and any constraints that are associated with the tasks. At a minimum, the constraints associated with the tasks must identify each of the resources assigned to the task, and the work-amount that each resource must perform. Next, assignments are generated for each of the tasks. Each of the assignments must identify a specific resource and the work-amount required by the specific resource. Finally, each of the assignments are scheduled in accordance with the provided resource constraints identified in the resource calendar.
Alternative embodiments of the present invention may provide additional resource and task constraints. In one embodiment, the resource constraints can identify time-slots in which each of the resources are available to work on assignments. In another embodiment, the resource constraints can identify the earliest date that each of the resources are available to work on the assignments. In addition the task constraints can include one or more scheduling constraints which may limit the manner in which the assignments are scheduled.
The scheduling process of the present invention can be performed in several ways. In one embodiment of the present invention, the resource constraints identify time-slots for the resources. The time-slots are spans of time that assignments can be scheduled to the resources. The scheduling process then includes sequentially selecting each of the assignments which identify a particular resource, and associating the assignments with the first available time-slot in the resource calendar for that particular resource. After all of the assignments for that particular resource have been scheduled the process is repeated for each of the other resources. This process results in maximizing the utilization of the resource by eliminating idle times.
In another embodiment, the task constraints include at least one scheduling constraint which is used as a basis for placing the assignments into a scheduling order. The scheduling process then includes sequentially selecting the assignments in accordance with the scheduling order.
In yet another embodiment, the task constraints include one or more scheduling constraints. The assignments are then placed into groups based on a function of the scheduling constraints. Furthermore, a priority is assigned to each group based on another function of the scheduling constraints. Finally, each assignment in each group is ordered based on a specific function of the scheduling constraints identified for each group.
In still another embodiment, four functions are used to place the assignments into one of four groups. The first function forms a first group by selecting assignments of tasks with a scheduling constraint which identifies a date on which the task must start. The second function forms a second group by selecting assignments of tasks with a scheduling constraint which identifies a date by which the task must be completed. The third function forms a third group by selecting assignments of tasks which are not dependent on the completion of any other tasks. The fourth function forms a fourth group by selecting all of the remaining assignments.
The scheduling process for the above-described embodiment could include scheduling each of the assignments in the following manner. First, scheduling the assignments in the first group into a time-slot for the assigned resources which correspond with the date that the assignments must begin. Then, scheduling the assignments in the remaining groups by selecting an assignment from the third group and scheduling the selected assignment if: (1) there are no assignments in the fourth group with a higher priority; and (2) there are no assignments in the second group that could not be finished by the required date if the selected assignment is scheduled. If condition (1) is not valid, then the scheduling of the assignment selected from the third group is postponed. If condition (2) is not valid, then the assignments in the second group that could not be finished will be scheduled before the selected assignment is scheduled. In addition, if all of the assignments for a task have been scheduled, then any tasks that are dependent on the scheduled task are examined. If it is determined that any of these tasks are not dependent on any other unscheduled tasks, then all of the assignments for these tasks which are currently in the fourth group are moved to the third group. This process continues until all of the assignments have been scheduled.
In view of the foregoing, it will be appreciated that the present invention provides the advantage of generating a schedule which maximizes the utilization of.available resources. It will also be appreciated that the present invention provides the advantage of generating a schedule which is assignment-oriented rather than task-oriented. It will also be appreciated that the present invention can generate a meaningful schedule for a set of non-dependent tasks without requiring the input of artificial constraints such as start dates or dependencies. It will also be appreciated that the present invention generates a balanced schedule. Furthermore, the present invention efficiently and quickly generates a balanced schedule which maximizes the utilization of available resources. It will also be appreciated that the present-invention subdivides a task or assignment into components which can be individually scheduled, and generates a maximum resource utilization schedule based on these components.